package com.cb2.algorithm.leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href='https://leetcode.cn/problems/merge-two-binary-trees/'>合并二叉树</a>
 * <p>给你两棵二叉树： root1 和 root2 。</p>
 * <p>想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。</p>
 * <p>返回合并后的二叉树。</p>
 * <p><p>注意:</p> 合并过程必须从两个树的根节点开始。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
 *              1               2                      3
 *            /  \            /   \                  /   \
 *           3    2          1     3       ==>      4     5
 *          /                 \     \             /  \     \
 *         5                   4     7           5    4     7
 *      输出：[3,4,5,5,4,null,7]
 *
 *  示例 2：
 *      输入：root1 = [1], root2 = [1,2]
 *      输出：[2,2]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>两棵树中的节点数目在范围 [0, 2000] 内</li>
 *     <li>-10^4 <= Node.val <= 10^4</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/2/10 17:23
 */
public class LC0617MergeTwoBinaryTrees_S {

    static class Solution {
        public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
            //return mergeTreesByIterator(root1, root2);
            return mergeTreesByRecursion(root1, root2);
        }

        private TreeNode mergeTreesByIterator(TreeNode root1, TreeNode root2) {
            if (root1 == null) {
                return root2;
            }
            if (root2 == null) {
                return root1;
            }
            TreeNode merged = new TreeNode(root1.val + root2.val);
            Queue<TreeNode> queue = new LinkedList<>();
            Queue<TreeNode> queue1 = new LinkedList<>();
            Queue<TreeNode> queue2 = new LinkedList<>();
            queue.offer(merged);
            queue1.offer(root1);
            queue2.offer(root2);
            while (!queue1.isEmpty() && !queue2.isEmpty()) {
                TreeNode node = queue.poll();
                TreeNode node1 = queue1.poll();
                TreeNode node2 = queue2.poll();
                if (node == null || node1 == null || node2 == null) {
                    continue;
                }
                TreeNode left1 = node1.left;
                TreeNode left2 = node2.left;
                TreeNode right1 = node1.right;
                TreeNode right2 = node2.right;

                if (left1 != null || left2 != null) {
                    if (left1 != null && left2 != null) {
                        TreeNode left = new TreeNode(left1.val + left2.val);
                        node.left = left;
                        queue.offer(left);
                        queue1.offer(left1);
                        queue2.offer(left2);
                    }else if (left1 != null) {
                        node.left = left1;
                    //} else if (left2 != null) {
                    } else {
                        node.left = left2;
                    }
                }
                if (right1 != null || right2 != null) {
                    if (right1 != null && right2 != null) {
                        TreeNode right = new TreeNode(right1.val + right2.val);
                        node.right = right;
                        queue.offer(right);
                        queue1.offer(right1);
                        queue2.offer(right2);
                    } else if (right1 != null) {
                        node.right = right1;
                    //} else if (right2 != null) {
                    } else {
                        node.right = right2;
                    }
                }
            }
            return merged;
        }

        private TreeNode mergeTreesByRecursion(TreeNode root1, TreeNode root2) {
            if (root1 == null) {
                return root2;
            }
            if (root2 == null) {
                return root1;
            }
            TreeNode mergeNode = new TreeNode(root1.val + root2.val);
            mergeNode.left = mergeTrees(root1.left, root2.left);
            mergeNode.right = mergeTrees(root1.right, root2.right);
            return mergeNode;
        }
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(3);
        root1.right = new TreeNode(2);
        root1.left.left = new TreeNode(5);

        TreeNode root2 = new TreeNode(2);
        root2.left = new TreeNode(1);
        root2.right = new TreeNode(3);
        root2.left.right = new TreeNode(4);
        root2.right.right = new TreeNode(7);

        Solution solution = new Solution();
        Printer.printTreeNode(solution.mergeTrees(root1, root2));
    }
}
